Combinatorial Problems (Permutations, Combinations)

Combinatorics হলো গণনা বা গণনা করা সমস্যা যা একাধিক উপাদান থেকে নির্বাচন করার পদ্ধতিগুলি গবেষণা করে। এর মধ্যে permutations এবং combinations দুইটি গুরুত্বপূর্ণ সমস্যা অন্তর্ভুক্ত।

• Permutations হল একটি নির্দিষ্ট সেটের মধ্যে উপাদানগুলোর বিভিন্ন排列 (arrangements), যেখানে প্রতিটি উপাদান একবার এবং একটি নির্দিষ্ট ক্রমে ব্যবহার করা হয়।
• Combinations হল একটি নির্দিষ্ট সেট থেকে উপাদান নির্বাচন করার পদ্ধতি, কিন্তু এখানে ক্রম গুরুত্বপূর্ণ নয়।

এখানে, আমরা Permutations এবং Combinations সম্পর্কিত সমস্যাগুলি Java তে কীভাবে সমাধান করা যায় তা আলোচনা করব।

1. Permutations (পরমুটেশন)

Permutations একটি সেটের উপাদানগুলোর সকলে ভিন্ন ভিন্ন সাজানো সংস্করণগুলির সংখ্যা বা তালিকা। n উপাদান থেকে r উপাদান নির্বাচন করে সাজানোর জন্য ব্যবহার করা হয়।

1.1. Permutations Formula

• nPr (n উপাদান থেকে r উপাদান নির্বাচন): $$P(n, r) = \frac{n!}{(n - r)!}$$

এটি factorial ব্যবহার করে গণনা করা হয়, যা একটি পজিটিভ ইন্টিজারের জন্য গুণফল গণনা করে।

1.2. Permutations Example in Java

import java.util.*;

public class Permutations {
    
    // Function to print all permutations of a given string
    public static void permute(String str, int l, int r) {
        if (l == r) {
            System.out.println(str);
        } else {
            for (int i = l; i <= r; i++) {
                // Swap characters at positions l and i
                str = swap(str, l, i);
                permute(str, l + 1, r); // Recur for the next character
                // Swap back (backtrack)
                str = swap(str, l, i);
            }
        }
    }

    // Utility function to swap characters
    private static String swap(String str, int i, int j) {
        char[] charArray = str.toCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return new String(charArray);
    }

    public static void main(String[] args) {
        String str = "ABC";
        int n = str.length();
        permute(str, 0, n - 1);
    }
}

ব্যাখ্যা:

• permute() ফাংশনটি একটি স্ট্রিংয়ের সব permutations তৈরি করতে সাহায্য করে।
• swap() ফাংশনটি দুইটি চরিত্রের স্থান বদলানোর জন্য ব্যবহৃত হচ্ছে।
• Backtracking: স্ট্রিংয়ের প্রতিটি চরিত্রের পরিবর্তন করার পর, পূর্বাবস্থায় ফিরিয়ে আনা হয়।

আউটপুট:

ABC
ACB
BAC
BCA
CBA
CAB

2. Combinations (কম্বিনেশন)

Combinations হল একটি সেটের অংশ নির্বাচন করার পদ্ধতি, যেখানে নির্বাচন করা উপাদানগুলোর ক্রম কোন গুরুত্ব রাখে না।

2.1. Combinations Formula

• nCr (n উপাদান থেকে r উপাদান নির্বাচন): $$C(n, r) = \frac{n!}{r!(n - r)!}$$

এটি একটি পদ্ধতি যা নির্ধারণ করে যে একটি নির্দিষ্ট সেট থেকে কতভাবে উপাদান নির্বাচন করা যায়, যখন ক্রম গুরুত্বপূর্ণ নয়।

2.2. Combinations Example in Java

import java.util.*;

public class Combinations {
    
    // Function to generate combinations
    public static void combine(int n, int r) {
        int[] data = new int[r];
        printCombination(n, r, 0, data, 1);
    }

    // Utility function to print combinations
    private static void printCombination(int n, int r, int index, int[] data, int i) {
        if (index == r) {
            for (int j = 0; j < r; j++) {
                System.out.print(data[j] + " ");
            }
            System.out.println();
            return;
        }

        if (i > n) return;

        // Include current element
        data[index] = i;
        printCombination(n, r, index + 1, data, i + 1);

        // Exclude current element and move forward
        printCombination(n, r, index, data, i + 1);
    }

    public static void main(String[] args) {
        int n = 5, r = 3;
        combine(n, r);
    }
}

ব্যাখ্যা:

• combine() ফাংশনটি n এবং r এর মান দিয়ে r উপাদানের সমস্ত সম্ভাব্য combinations তৈরি করতে সাহায্য করে।
• printCombination() ফাংশনটি একটি recursive পদ্ধতিতে কাজ করে, যেখানে প্রথমে উপাদানগুলো নির্বাচন করা হয়, তারপর ক্রম অনুসারে তাদের কম্বিনেশন তৈরি করা হয়।

আউটপুট:

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

3. Permutations vs Combinations

4. Applications of Permutations and Combinations

• Permutations:
  • Cryptography: For generating possible keys or combinations.
  • Puzzle solving: Arranging puzzle pieces.
  • Scheduling problems: Determining different schedules or orders for tasks.
• Combinations:
  • Lottery: Determining possible combinations of lottery numbers.
  • Team selection: Choosing teams from a group of people, without considering the order.
  • Subsets: Finding all possible subsets of a given set.

সারাংশ

Permutations এবং Combinations হল Combinatorial Problems যা গণনা বা নির্বাচন করার বিভিন্ন পদ্ধতি সম্পর্কে আলোচনা করে। Permutations হল যখন আপনি একটি সেটের উপাদানগুলোর বিভিন্ন সাজানো ভিন্ন ভিন্ন সংস্করণ তৈরি করেন, যেখানে Combinations হল যখন আপনি একটি সেট থেকে উপাদান নির্বাচন করেন, তবে সেখানে সাজানোর গুরুত্ব থাকে না। উভয় সমস্যা Java তে recursive এবং iterative পদ্ধতিতে সমাধান করা যায়, এবং প্রতিটি পদ্ধতির নিজস্ব ব্যবহারিক ক্ষেত্রে উপকারী।